public class Solution3 {
    //1745. 分割回文串 IV
    public boolean checkPartitioning(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];

        for (int i = n - 1; i >= 0 ; i--) {
            for (int j = i; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (i == j) {
                        dp[i][j] = true;
                    } else if (i + 1 == j) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
            }
        }
        for (int i = 1; i < n -1; i++) {
            for (int j = i; j < n-1; j++) {
                if (dp[0][i-1] && dp[i][j] && dp[j+1][n-1]) {
                    return true;
                }
            }
        }
        return false;

    }
}
